With the continually wider use of electronic methods of communication and information storage, secrecy has become an imperative requirement, particularly for important documents such as bank statements, contracts, and the like. While the problem of data protection has received some legislative attention, the technical problems of protecting data to be transmitted have not been satisfactorily solved. Radio transmission or broad band cable transmission of secret data is currently more or less public, and exposed to interception. Currently, there is not any guarantee that secret data can be kept confidential when transmitted. Technical means currently in use do not protect against the decoding of secret data when the data is transmitted by radio or wire. The user must adopt his own steps to ensure confidentiality, such as by ensuring the authenticity of the sender, and protecting against manipulation of the message.
To ensure security therefore, it is important that the information to be transmitted (data, texts, etc.), be converted to a form which cannot be decrypted by an unauthorized person. It has also been found that in general, that the more complex the operations underlying a cipher, the more secure it is.
In classical encryption techniques, symmetrical methods are employed wherein the keys for encryption and decryption are similar, i.e. are identical or inverted. As long as the key is kept secret, the encrypted message can be publicly transmitted. However, in order to decrypt the message, the recipient must be supplied with the secret key by means of a confidential channel, such as a courier. The transmission of a secret key is inconvenient and time-consuming, particularly if one confidential message is broadcast to a number of recipients. Certainly in the electronic age, it is anachronistic to employ couriers or the like to transmit secret keys.
Against this background, ciphers by so-called "public key code" methods have been received as a major advance. Such methods are characterized by an asymmetric key. This means that two different keys are used, one for encrypting and the second for decrypting. With the asymmetric method, one key cannot be determined from the other without additional information. Therefore one of the two keys may be publicized without hazard. It is for this reason that this method has been designated as "public key code".
If a user of the public network exchanges messages with other subscribers by means of the "public key code" method, he must first produce two keys, E and D. By means of a public register, the key E is made available to all other users for encryption, but the decryption key D is kept secret. With many of these methods, the general computation algorithms for encoding are publicized, but doing so does not endanger the secrecy of the contents of the encrypted messages. In addition, the authenticity of the message is not a problem. The security of the asymmetric method rests on the fact that it is practically impossible to compute D from E.
A person who wishes to send a message to another user obtains the key E from the public register, and uses it to encrypt the message. The resulting code is transmitted over an insecure network (possibly digital), e.g. the public telephone network. The recipient decrypts the code received, by means of his secret key D, thereby generating the original message. Thus, a secure channel is not needed to transmit one of the keys, nor to transmit the message itself. The recipient only receives messages which have been encrypted with his own key. The only thing which he needs to obtain independently is the special key D.
Thus by this technique, the main body of the keys are readily available, and the user is relieved from the burden of managing a massive personal key register. Management, i.e., data entry of the keys occurs only once, and this is located centrally in a register which is accessible to all users, a register which is in the nature of an electronic telephone book or an electronic bulletin board This "public key code" transmission procedure can be employed to make any type of transmission network such as ISDN secure.
The above-described embodiment of a "public key code" method still does not authenticate the sender or protect against tampering with the message. In principle it is possible to transmit a digital "signature" which cannot be counterfeited, particularly if the sequence of application of keys D and E is permutable. Then the sender can generate a signature which is transmitted with the encrypted message. This signature is an "extract" of the message, and the extract is encrypted with the secret key D used as a sender key. To test the authenticity of the sender, the recipient generates the extract from the reconstructed message, decrypts the signature with the public sender key E, and compares the two. If they are identical, the message must be from the identified sender, because only the sender and not an impostor knows the key D which matches the sender key E, with which key D the signature was encrypted.
The signature also protects the message against tampering. Moreover, the sender cannot disavow or dispute the message, because the recipient is in possession of a signature in the message. Likewise, the recipient cannot alter the message, because he cannot generate a signature for the counterfeit message. The reason is that the signature, on account of the extract, depends not only on the identity of the sender but also on the message itself. Therefore a higher degree of protection is afforded than with a signature on an ordinary document.
The well-known "public key code" method is called the "RSA" method in honor of its inventors, Rivest, Shamir, and Adleman. The security of the RSA method is based on the fact that it is practically impossible to factor large numbers (e.g., of 200 decimal places), to find all the prime numbers into which the large numbers can be divided without remainders.
The RSA method operates as follows: First, each user of the RSA system selects two large prime numbers, p and q, and a third large number, E (not identical to the key E mentioned earlier). The numbers can be generated by a random number generator of a computer. Algorithms are available to verify that a given number is a prime number (see, e.g., Pomerance, C. (Univ. of Georgia, [U.S.A.]), 1981, "Recent developments in primality testing", in "The Mathematical Intelligencer," Vol. 3, Nr. 3, pp. 97-104).
The RSA method does not prescribe a minimum length for the prime numbers. Small numbers make the algorithms faster, but increase the risk that the product of the prime numbers can be factored. The inverse is true of large numbers. In general, 100 decimal digits is regarded as a good compromise. Let N be the product of the primes p and q. The pair (E, N) is the public key, while the primes p and q are known only to the recipient of a message.
To encrypt the message, the sender first converts his text into a sequence of decimal numbers. This sequence is then divided into elements P.sub.i of equal length i.e., each element having an equal number of decimal digits, with P.sub.i &lt;N. These elements are then individually encrypted by raising them to the Eth power and forming modulus N. Thus the numbers EQU C.sub.i =P.sub.i.sup.E modulus N
are generated, which are then transmitted over an insecure channel. To evaluate the numbers, one calculates their exponents modulus .phi.(N), where EQU .phi.(N) = (p-1)(q-1).
Since only the recipient knows the primes p and q, only he can compute the key EQU D= E.sup.-1 modulus .phi.(N).
The recipient raises each received number C.sub.i to the Dth power and reduces modulus N. Since EQU C.sub.i.sup.D modulus N=P.sub.i.sup.ED modulus N, and EQU ED modulus .phi.(N)=1,
the operation EQU P.sub.i.sup.ED modulus N
regenerates the original number fragments of the text.
The classical encryption method and the "public key code" methods all have major drawbacks. Both the software and the hardware involved in implementing the prior art methods have proven impractical due to very high costs.
With the current state of chip development, it is not possible to program a general purpose computer with the RSA algorithm (on the basis of 200 decimal digits) to yield acceptable encryption speeds and rates. Also, the RSA function (involution followed by modulus reduction) cannot be carried out directly in a VLSI (Very Large Scale Integration) layout, because there are no direct involution circuits. Thus, for many years it has been desirable to have special hardware which will break down involution into individual steps such that sufficient speeds and rates of encryption are possible.
Nonetheless, currently known implementations of the "public key code" method require a great deal of computing time. Software developed for general purpose computers has encryption and decryption rates of only 10-20 bit/sec. Even the best of the known hardware solutions delivers not more than 1,200 bit/sec. The only single chip solution achieved thus far was developed by Rivest (Rivest, R. L., (Laboratory for Computer Science, MIT), 1980, "A description of a single-chip implementation of the RSA cipher", in LAMBDA Magazine 1, 3:14-18). With this proposal, a relatively simple design was chosen wherein a 512-bit wide arithmetic logic unit (ALU) was constructed using an ordinary arithmetic logic elementary cell. The structure of this ALU allowed it to carry out a very wide variety of operations. The redundancy employed resulted in an encryption rate of 1,200 bit/sec, using a 4-micron NMOS technology. Extrapolated to a 2-micron CMOS technology, an encryption rate of in the range of 2,500 bit/sec could be achieved with a key length of 660 bits using the same general approach.
However, from a practical standpoint this solution is still unacceptable, because system interfaces in the data networks operate at very high data rates. For example ISDN interfaces operate at 64 kbit/sec.
A cryptography processor has been proposed which is comprised of two chips and which can be used for processing 336-bit long numbers employed in the RSA algorithm (see Rieden, R. F., Snyder, J. B., Widman, R. J., and Barnard, W. J., 1982, "A two-chip Implementation of the RSA Public-Key Encryption Algorithm", in "Digest of papers for the 1982 Government Microcircuit Applications Conference", Nov. 1982, pp. 24-27).
The fastest known RSA processor is that disclosed with the proposal of NEC/Miyaguchi (Miyaguchi, S., [1982],"is converted to Fast Encryption Algorithm for the RSA Cryptographie System", in "Proceedings COMPCON 82"). It operates with 8 bits of the multiplier per cycle, and thereby reaches a speed of 29,000 bit/sec. However, since for practical application it requires the high number of 333 chips, it is obviously economically impractical.
A general disadvantage of multi-chip implementations is not only the increase in hardware costs which increases proportionally to the number of chips required, but also the decrease in security. If the signals passing from one chip to another are accessible, then the secret code can be broken with the aid of the transferred signals. Therefore, it is crucial from the standpoint of cryptographic security that all cryptography algorithms be protected by a single chip, via a secure mode of housing the chip.
In German Patent No. 3,228,018, a key system for RSA cryptography is described which also requires a major hardware commitment. In comparison to the original RSA algorithm, with the known key system i.e. the system proposed in the Ger. Pat. No. 3,228,018, encryption rates are only increased by a factor of 4, a modest improvement. To achieve the improvement, a fixed number of bits, namely 4 bits, are processed simultaneously, requiring a plurality of multipliers. A total of 14 adders are also used.
Theoretically, it is conceivable that the processor for the key system of Ger. Pat. No. 3,228,018 achieves a speed four times that of the direct use of the original RSA algorithm. However, the signal paths are much longer than with single bit processing, in which a single bit is read at a time, and therefore in practice very little speed advantage can be expected.
A universal chip with 100 fold computation density also would not be able to carry out the known RSA algorithm with a speed improvement, for reasons other than its raw bit processing rate. Accordingly, the only candidate to achieve rate improvements, if any, would be a special cryptography chip. In any event, substantial cooling problems would be presented, because in such a highly specialized chip, all the transistor functions would be in operation almost constantly , in contrast to the situation with a universal chip. This would be accompanied by substantial power dissipation, resulting in a 100 fold increase in dissipation density over the dissipation density experienced for general computing with a universal chip.
The cooling problem would therefore be substantial, as indicated by the costly proposal in Ger. Pat. No. 3,228,018, whereby cooling is performed by passing a noble gas through channels in the silicon chip. Without adequate cooling, the service life of the chip would be shortened substantially, and the error rate in the cryptography operations would be increased. Furthermore, the universal chip with high computation density would have to be of such excessive size as to defeat its practical implementation.